package com.cat.dataStructure02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description 'https://leetcode.cn/problems/maximum-frequency-of-an-element-after-performing-operations-i/?envType=daily-question&envId=2025-10-21
 * @create 2025/10/21 11:58
 * @since JDK17
 */

public class Solution33 {
    static int N = ((int) (1e5 + 10));
    static int[] h = new int[N], prefix = new int[N];

    public int maxFrequency(int[] nums, int k, int m) {
        int n = nums.length, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, ans = 0;
        Arrays.fill(h, 0);
        Arrays.fill(prefix, 0);
        for (int num : nums) {
            h[num]++;
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        for (int i = min; i <= max; i++) { // 前缀和数组
            prefix[i] += prefix[i - 1] + h[i];
        }
        for (int i = min; i <= max; i++) {
            int l = i - k - 1 >= 0 ? prefix[i - k - 1] : 0;
            int r = i + k <= max ? prefix[i + k] : prefix[max];
            ans = Math.max(ans, Math.min(r - l, m + h[i]));
        }

        return ans;
    }
}
